/**
 * Pascal's Triangle
Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
 */
package com.xinpan.exercise;

import java.util.ArrayList;

public class PascalTriangle {
    public ArrayList<ArrayList<Integer>> generate(int numRows) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> pt = new ArrayList<ArrayList<Integer>>();
        if(numRows == 0)
            return pt;
        
        ArrayList<Integer> row = new ArrayList<Integer>();
        row.add(1);
        pt.add(row);
        if(numRows == 1)
            return pt;
        
        for(int i = 1; i < numRows; i++)
        {
            row = new ArrayList<Integer>();
            for(int j = 0; j <= i; j++)
            {
                int val;
                if(j == 0 || j == i)
                    val = 1;
                else
                    val = pt.get(i-1).get(j-1) + pt.get(i-1).get(j);

                row.add(val);
            }
            pt.add(row);
        }
        
        return pt;
    }
}
